package Z.dailyExercise.March;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

public class _剑指Offer59II队列的最大值 {

    Queue<Integer> queue ;
    Deque<Integer> maxDeque;//求最大值的双端队列

    public _剑指Offer59II队列的最大值() {
        this.queue = new LinkedList<>();
        this.maxDeque = new ArrayDeque<>();

    }

    public int max_value() {

        if (!maxDeque.isEmpty()){
            return maxDeque.peekFirst();
        }else {
            return -1;
        }

    }

    public void push_back(int value) {
        queue.add(value);
        while (!maxDeque.isEmpty() && maxDeque.peekLast() < value){
            maxDeque.pollLast();
        }
        maxDeque.offerLast(value);

    }

    public int pop_front() {
        if (queue.isEmpty() ){
            return -1;
        }
        int num = queue.poll();
        if ( !maxDeque.isEmpty() &&maxDeque.peekFirst() == num){
                maxDeque.pollFirst();
        }

        return num;




    }
}
